package algorthm.systemTraning.mergeSort.ReversePair;

import org.apache.poi.util.StringUtil;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @className: ReversePair
 * @Description: 给定一个数组，如果 An > Am  n != m 则称 (An , Am)为一个逆序对,
 * 找出所有的逆顺对
 * @Author: wangyifei
 * @Date: 2022/9/22 10:43
 */
public class ReversePair {
    private static Logger logger = LoggerFactory.getLogger(ReversePair.class);
    public static class RPair{
        private int n1 ;
        private int n2 ;
        public RPair(int n1 , int n2){
            this.n1 = n1 ;
            this.n2 = n2 ;
        }

        public int getN1() {
            return n1;
        }

        public void setN1(int n1) {
            this.n1 = n1;
        }

        public int getN2() {
            return n2;
        }

        public void setN2(int n2) {
            this.n2 = n2;
        }

        @Override
        public String toString() {
            return (n1<10?"0"+n1:n1) + ":" + (n2<10?"0"+n2:n2) ;
        }
    }
    public static List<RPair> mergeSort(int[] array , int start , int end){
        if(array == null || array.length == 0){
            return null ;
        }
        if((end - start) == 0){
            return null ;
        }
        int mid = (end + start) >> 1 ;
        List<RPair> l1 = mergeSort(array , start , mid);
        List<RPair> l2 = mergeSort(array , mid + 1 , end);
        List<RPair> merge = merge(array, start, mid, end);
        if(null != l1){
            merge.addAll(l1);
        }
        if(null != l2){
            merge.addAll(l2);
        }
        return merge;
    }
    public static List<RPair> merge(int[] array , int start , int mid , int end){
        int a1 = start ;
        int a2 = mid + 1;
        int[] merge = new int[end - start + 1];
        List<RPair> list = new ArrayList<>();
        int i = 0 ;
        while(a1<=mid && a2<=end){
            if(array[a1] <= array[a2]){
                merge[i++] = array[a1++];
            }else{
                for(int q = a1 ; q <= mid ; q++){
                        list.add(new RPair(array[q] , array[a2]));
                }
                merge[i++] = array[a2++];
            }
        }
        while(a1<=mid){
            merge[i++] = array[a1++];
        }
        while(a2<=end){
            merge[i++] = array[a2++];
        }
        for(int j = 0 ; j < merge.length ; j++){
            array[start + j] = merge[j];
        }
        return list ;
    }

    public static void main(String[] args) {
//        int[] array = { 11 , 1 , 12 , 4} ;
//        int[] array = {34, 34, 15, 27, 74, 99} ;
        int[] array = {36, 18, 23, 31, 19, 69, 26, 23, 43, 2};
        //  18:02,19:02,23:02,23:02,23:19,26:02,26:23,31:02,31:19,31:23,31:26,36:02,36:18,36:19,36:23,36:23,36:26,36:31,43:02,69:02,69:23,69:26,69:43
        List<RPair> rPairs = mergeSort(array, 0, array.length - 1);
        Comparator<RPair> comparator = new Comparator<ReversePair.RPair>() {
            @Override
            public int compare(ReversePair.RPair o1, ReversePair.RPair o2) {
                return o1.toString().compareTo(o2.toString());
            }
        };
        System.out.println(rPairs.stream().sorted(comparator).map(x -> x.toString()).collect(Collectors.joining(",")));
    }
}
